Родился в уездном г. Короча Курской губернии (ныне районный центр Белгородской области) в дворянской семье.
Окончил 2-ю Санкт-Петербургскую военную гимназию.
В 1875 г. — Николаевское инженерное училище (ныне Военный инженерно-технический университет).
Участвовал в русско-турецкой войне 1877—1878 гг., где состоял сначала в 1-м саперном батальоне, затем во 2-м военно-телеграфном парке.
Участвовал в разработке Твердицкого перевала между горой Еленой с севера и селением Твердицей на юге Балкан.
В 1881 г. окончил Николаевскую инженерную академию, причём он был первым по успеваемости и его имя занесено на мраморную доску. Благодаря этому Величко оставлен при академии преподавателем, занимал должность репетитора по фортификации.
В 1883 г. командирован за границу в Берлинский университет для слушания лекций и затем практически изучал технические производства в Германии, Франции, Италии, Англии и Бельгии.
C 1890 г. — профессор Николаевской инженерной академии по кафедре фортификации, оставался на этой должности до начала русско-японской войны 1905.
В 1892—1893 г. полковник Величко работал в крепостях Ковно и Новогеоргиевске, где заведовал сооружением крепостных железных дорог и принимал участие во всех занятиях гарнизонов.
В 1893 г. — член комиссии по вооружению крепостей.
В 1895 г. — управляющий делами этой комиссии.
Участвовал также во многих других комиссиях и комитетах.
С 1903 г. — помощник начальника Главного военно-инженерного управления (ГВИУ).
Во время русско-японской войны служил генералом для поручений при главнокомандующем, руководил военно-инженерными работами в Маньчжурии, являлся автором проектов укреплений Владивостока и Порт-Артура.
В 1884-1910 гг. — автор ряда статей по крепостным вопросам в «Инженерном журнале», «Военном сборнике», «Русском инвалиде» и «Разведчике», а также в газетах Новое время, Санкт-Петербургские ведомости и др.
С 1910 г. Величко — главный редактор Военной энциклопедии (СПб, 1911, т-во И. Д. Сытина).
В годы 1-й мировой войны (1914–1918) — начальник инженеров Юго-Западного фронта. Предложил новую форму инженерного оборудования местности для наступления — «инженерные плацдармы». Впервые такой плацдарм создан при подготовке брусиловского прорыва.
В 1917 г. занимал высший инженерный пост полевого инспектора инженерной части при Ставке ВГК.
В ноябре 1917 г. Величко перешёл на сторону Советской власти.
В феврале 1918 г. добровольно вступил в Красную Армию, руководил инженерной обороной Петрограда.
С марта 1918 г. — председатель коллегии по инженерной обороне государства при Гл. инженерно-техническом управлении Рабоче-Крестьянской Красной армиии (РККА), преподавал инженерное дело в Военной академии РККА.
С января 1919 г. — член инженерного комитета ГВИУ.
В 1923 г. — профессор фортификации в Военно-инженерной академии.
Величко — автор свыше 70 трудов по военно-инженерному искусству, внёс крупный вклад в его развитие.
В приказе РВСР № 2731 от 8 декабря 1922 г. отмечалось, что «громадная работа, проделанная профессором Величко по изучению и использованию опыта мировой войны, дала возможность устранить недочеты прошлых лет при укреплении наших рубежей... Имя профессора Величко стоит наряду с самыми крупными именами в области фортификации».
Скончался в Ленинграде. Похоронен на Никольском кладбище Александро-Невской Лавры.
Награды: многие, русские императорские и советские ордена, иностранные ордена.
Соч.:
За и против броневых закрытий в крепостях. 1985;
Исследование новейших средств осады и обороны сухопутных крепостей. Спб., 1890;
Оборонительные средства крепостей против ускоренных атак. Спб., 1892;
Крепости и крепостные железные дороги. 1897;
Условия работ и жизнь войск на Квантуне. 1900;
Инженерная оборона государств и устройство крепостей. Ч. 1. Сухопутные крепости. Спб., 1903;
Крепости до и после мировой войны. 1914—1918 гг. М., 1922;
Русские крепости в связи с операциями полевых армий в мировую войну. Л., 1926;
Четырехлетняя война 1914–1918 г. и ее эпоха. Роль крепостей в связи с операциями полевых армий;
Ист:
Советская военная энциклопедия (в 8-ми т.). М., Воениздат, 1976 – 1980;
Богатский М. Военный инженер К. И. Величко (1856 — 1927). М., 1957;
Выдающийся военный инженер.— «Воен.-ист. журн.», 1962, № 5;
Залесский, К. А. Кто был кто в первой мировой войне. Биографический энциклопедический словарь. М., 2003.